// 230.二叉搜索树中第K小的元素
package Leetcode_Second_Brush;

public class Solution230 {
    public int kthSmallest(TreeNode root, int k) {
        int leftNodes = countNodes(root.left);
        if (leftNodes < k - 1) {
            return kthSmallest(root.right, k - leftNodes - 1);
        } else if (leftNodes == k - 1) {
            return root.val;
        } else {
            return kthSmallest(root.left, k);
        }
    }

    // 计算节点数
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        int leftNodes = countNodes(root.left);
        int rightNodes = countNodes(root.right);
        return leftNodes + rightNodes + 1;
    }
}
